home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-01 / ddj9304.zip / 1993-APR.ZIP / DIFFCOMP.ASC < prev    next >
Text File  |  1993-02-17  |  8KB  |  226 lines
  1. _DIFFERENTIAL COMPRESSION ALGORITHMS_
  2. by James H. Sylvester
  3.  
  4. [LISTING ONE]
  5.  
  6. /****************************************************************************/
  7. /*  PACK.C -- by James Sylvester                                            */
  8. /****************************************************************************/
  9.  
  10. #include <stdio.h>
  11.  
  12. void main(int argc, char *argv[])
  13. {
  14.   const blockfactor = 1;              /* adjust as desired */
  15.   const blocksize = blockfactor * 8;
  16.   char  buffer [257] [8];             /* enter blocksize for second index */
  17.  
  18.   int   i, j, currentsize;
  19.   FILE  *sf, *tf;               /* sourcefile & targetfile respectively */
  20.   int   bestblock;              /* best matching block in buffer */
  21.   int   bestcount, matchcount;
  22.   int   changeindex, bitvalue;
  23.  
  24. /* Verify and perform error handling for opening both the input file and   */
  25. /* the output file as binary files.  Note, the input file has the original */
  26. /* data and the output file will contain the encoded/compressed data.      */
  27.   if (argc != 3)
  28.   {
  29.     printf("Correct usage is  >pack source_filename target_filename\n");
  30.     exit(1);
  31.   }
  32.   if ((sf = fopen(argv[1], "rb"))==NULL)  /* read only mode for input file */
  33.   {
  34.     printf("Unable to open source file %s\n", argv[1]);
  35.     exit(2);
  36.   }
  37.   if ((tf = fopen(argv[2], "wb"))==NULL)  /* write only mode for output file */
  38.   {
  39.     printf("Unable to open target file %s\n", argv[2]);
  40.     exit(3);
  41.   }
  42. /* Initialize buffer with all zeros in the first block, all ones in the   */
  43. /* second block, and so forth so that there will be at least one matching */
  44. /* byte in the first block of input data regardless what it might be.     */
  45.   for (i = 0; i < 256; i++)
  46.     for (j = 0; j < blocksize; j++)
  47.       buffer [i] [j] = i;
  48.   while (1)  /* while true ==> stay in loop until internal exit */
  49.   {
  50. /* Load the next block of data from the sourcefile into the last slot of */
  51. /* the buffer.  Also, keep track of how many bytes were read to signify  */
  52. /* proper handling for the unfull block when at the end of file.         */
  53.     currentsize = blocksize;
  54.     for (j = 0; j < blocksize; j++)
  55.     {
  56.       i = getc(sf);
  57.       if (i == EOF)
  58.       {
  59.         currentsize = j;     /* reset correct currentsize */
  60.         break;               /* exit for loop */
  61.       }
  62.       buffer [256] [j] = i;  /* put character into last block */
  63.     }
  64.     if (currentsize == 0)    /* input data ended with previous full block */
  65.     {
  66.       printf("%s now contains encoded/compressed data!\n", argv[2]);
  67.       exit(4);
  68.     }
  69. /* Find the best matching block in buffer for the recently loaded block */
  70. /* of input data.  Afterwards, send the bestblock index to the output   */
  71. /* file and process the changes between the two blocks.                 */
  72.     bestcount = -1;
  73.     for (i = 0; i < 256; i++)
  74.     {
  75.       matchcount = 0;
  76.       for (j = 0; j < currentsize; j++)
  77.         if (buffer [i] [j] == buffer [256] [j])
  78.           matchcount++;
  79.       if (matchcount > bestcount)
  80.       {
  81.         bestcount = matchcount;
  82.         bestblock = i;
  83.         if (bestcount == currentsize)
  84.           break;                       /* exit for loop */
  85.       }
  86.     }
  87.     putc (bestblock, tf);
  88.     for (i = 0; i < blockfactor; i++)
  89.     {
  90.       changeindex = 0;
  91.       bitvalue = 1;
  92.       for (j = i*8; j < i*8+8; j++)
  93.       {
  94.         if (j >= currentsize)
  95.           break;
  96.         if (buffer [bestblock] [j] != buffer [256] [j])
  97.           changeindex += bitvalue;
  98.         bitvalue *= 2;
  99.       }
  100.       putc(changeindex, tf);
  101.       for (j = i*8; j < i*8+8; j++)
  102.       {
  103.         if (changeindex % 2 == 1)
  104.           putc(buffer [256] [j], tf);
  105.         changeindex /= 2;
  106.       }
  107.     }
  108.     if (currentsize < blocksize)  /* input data ended with unfull block */
  109.     {
  110.       putc(currentsize, tf);
  111.       printf("%s now contains encoded/compressed data!\n", argv[2]);
  112.       exit(5);
  113.     }
  114.     /* Update the best matching block in buffer with new data. Compression  */
  115.     /* should improve as further loaded blocks match exact copies in buffer */
  116.     for (j = 0; j < blocksize; j++)
  117.       buffer [bestblock] [j] = buffer [256] [j];
  118.   }
  119. }
  120.  
  121.  
  122. /****************************************************************************/
  123. /*  UNPACK.C -- by James Sylvester                                          */
  124. /****************************************************************************/
  125.  
  126. #include <stdio.h>
  127.  
  128. void main(int argc, char *argv[])
  129. {
  130.   const blockfactor = 1;              /* adjust as desired */
  131.   const blocksize = blockfactor * 8;
  132.   char  buffer [257] [8];             /* enter blocksize for second index */
  133.  
  134.   int   i, j;
  135.   FILE  *sf, *tf;        /* sourcefile & targetfile respectively */
  136.   int   bestblock = -1;  /* best matching block in buffer */
  137.   int   changeindex;
  138.  
  139. /* Verify and perform error handling for opening both the input file and the */
  140. /* output file as binary files. Input file contains encoded/compressed data */
  141. /* data and output file should contain an  exact copy of the original data. */
  142.   if (argc != 3)
  143.   {
  144.     printf("Correct usage is  >unpack source_filename target_filename\n");
  145.     exit(1);
  146.   }
  147.   if ((sf = fopen(argv[1], "rb"))==NULL)  /* read only mode for input file */
  148.   {
  149.     printf("Unable to open source file %s\n", argv[1]);
  150.     exit(2);
  151.   }
  152.   if ((tf = fopen(argv[2], "wb"))==NULL)  /* write only mode for output file */
  153.   {
  154.     printf("Unable to open target file %s\n", argv[2]);
  155.     exit(3);
  156.   }
  157. /* Initialize buffer with exactly same information as in PACK.C program. */
  158.   for (i = 0; i < 256; i++)
  159.     for (j = 0; j < blocksize; j++)
  160.       buffer [i] [j] = i;
  161. /* Reconstruct original data from encoded data in sourcefile. */
  162.   while (1)  /* while true ==> stay in loop until internal exit */
  163.   {
  164.     if (bestblock == -1)     /* input data yet to be loaded */
  165.     {
  166.       bestblock = getc(sf);
  167.       if (bestblock == EOF)  /* original and encoded files had 0 bytes */
  168.       {
  169.         printf("%s now contains reconstructed original data!\n", argv[2]);
  170.         exit(4);
  171.       }
  172.       changeindex = getc(sf);
  173.     }
  174.     else
  175.     {
  176.       bestblock = getc(sf);
  177.       if (bestblock == EOF)    /* input data ended with previous full block */
  178.       {
  179.         for (j = 0; j < blocksize; j++)  /* output full block */
  180.           putc(buffer [256] [j], tf);
  181.         printf("%s now contains reconstructed original data!\n", argv[2]);
  182.         exit(5);
  183.       }
  184.       changeindex = getc(sf);
  185.       if (changeindex == EOF)  /* input data ended with unfull block */
  186.       {
  187.         for (j = 0; j < bestblock; j++)  /* reinterpret bestblock as  */
  188.                                          /* last blocksize and output */
  189.                                          /* this last, partial block  */
  190.           putc(buffer [256] [j], tf);
  191.         printf("%s now contains reconstructed original data!\n", argv[2]);
  192.         exit(6);
  193.       }
  194.       for (j = 0; j < blocksize; j++)  /* output full block */
  195.         putc(buffer [256] [j], tf);
  196.     }
  197.     for (i = 0; i < blockfactor; i++)
  198.     {
  199.       if (i > 0)
  200.         changeindex = getc(sf);
  201.       for (j = i*8; j < i*8+8; j++)
  202.       {
  203.         if (changeindex % 2 == 1)
  204.           buffer [bestblock] [j] = getc(sf);  /* directly load changes */
  205.                                               /* into buffer bestblock */
  206.         changeindex /= 2;
  207.         buffer [256] [j] = buffer [bestblock] [j];  /* copy block info */
  208.       }
  209.     }
  210.   }
  211. }
  212.  
  213.  
  214. [LISTING THREE]
  215.  
  216.  
  217.         if (changeindex % 2 == 1)
  218.         { buffer [256] [j] = getc(sf); }
  219.         else
  220.         { buffer [256] [j] = buffer [bestblock] [j]; }
  221.         changeindex /= 2;
  222.       }         }
  223.   }
  224. }
  225.  
  226.